/**
 * 方法一 快速排序， 获取第 nums.length - k个元素
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
export function findKthLargestByQuicksort(nums, k) {
    /**
    * @param {*} arr 数组
    * @param {*} p  起始下标
    * @param {*} r  结束下标 + 1
    */
   const divide = (arr, p, r) => {
    const x = arr[r - 1];
    let i = p - 1;
    for(let j = p; j <  r - 1; j++) {
        if(arr[j] <= x) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]]
        }
    }

    [arr[i+1], arr[r-1]] = [arr[r-1], arr[i+1]]
    return i+1
}

/**
  * 
  * @param {*} A  数组
  * @param {*} p  起始下标
  * @param {*} r  结束下标 + 1
  */
 const quickSort = (arr, p = 0, r) => {
     r = r || arr.length;
     if(p < r - 1) {
         const q = divide(arr, p, r);
         quickSort(arr, p, q);
         quickSort(arr, q + 1, r)
     }
     return arr
 }
 const _arr = quickSort(nums);
 return _arr[_arr.length - k]
};



/**
 * 方法一 快速排序， 获取第 k-1个元素
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
export function findKthLargestByMaxHeap(nums, k) {
    // 堆的构建
    class BinaryHeap {
        constructor(capacity, compare, array) {
            if (array) {
                this.array = array.concat()
                this.size = array.length
                this.capacity = capacity < 3 ? this.size * 2 : capacity
            } else {
                if (capacity < 3) {
                    return null
                }
                this.array = new Array(capacity)
                this.size = 0
                this.capacity = capacity
            }
            this.compare = compare
        }
    
    
        // 检查二叉树是否为空
        isEmpty() {
            return this.size  === 0
        }
    
    
        // 获取节点i的父节点
        parent(i) {
            return (i - 1) / 2 | 0
        }
        // 获取节点i的左儿子
        left(i) {
            return 2 * i + 1
        }
        // 获取节点i的右儿子
        right(i) {
            return 2 * i + 2
        }
        // 根据数组元素索引进行交换
        swap(i, j) {
            let temp = this.array[i]
            this.array[i] = this.array[j]
            this.array[j] = temp
        }
        // 二叉堆push操作， 往堆中添加一个新元素
        push(T) {
            if(this.size === this.capacity) {
                console.log('overflow: could not push key')
                return
            }
            this.size++
            let i = this.size - 1
            this.array[i] = T
            // 上滤操作，由下而上检查
            while(i !== 0 && this.compare(this.array[i], this.array[this.parent(i)])) {
                this.swap(i, this.parent(i))
                i = this.parent(i)
            }
        }
        //获取堆顶元素
        top() {
            return this.array[0]
        }
        // 堆化操作，修复二叉树的性质，由上而下检查，又称为下滤操作
        heapify(i) {
            const left = this.left(i)
            const right = this.right(i)
            let small  = i
            if (left < this.size && this.compare(this.array[left], this.array[i])) {
                small = left
            }
            if (right < this.size && this.compare(this.array[right], this.array[small])) {
                small = right
            }
            if (small !== i) {
                this.swap(i, small)
                this.heapify(small)
            }
        }
        // 释放栈顶元素，降最后一个元素替换堆顶元素，然后进行下滤堆化操作
        pop() {
            if(this.size <= 0) {
                console.log('heap is empty')
                return
            }
            if (this.size === 1) {
                this.size--
                return this.array[0]
            }
            const root = this.array[0]
            this.array[0] = this.array[this.size - 1]
            this.size--
            this.heapify(0)
            return root
        }
    
    
        // 降低第i个结点的关键字
        decreaseKey(i, NT) {
            this.array[i] = NT
            while(i !== 0 && this.compare(this.array[i], this.array[this.parent(i)])) {
                this.swap(i, this.parent(i))
                i = this.parent(i)
            }
        }
        // 删除元素
        delete(i) {
            if(this.size === 0) {
                console.log('heap is empty')
                return
            }
            if(this.size === 1) {
                this.size--
                return
            }
            this.array[i] = this.array[this.size - 1]
            this.size--
            this.heapify(i)
        }
        // 构建堆
        build() {
            for(let i = this.size / 2 | 0; i >= 0; i --) {
                this.heapify(i)
            }
        }
    }

    // 主要实现步骤
    const h = new BinaryHeap(20, (a, b) => { return a >= b }, nums);
    h.build();
    let i = 0;
    let result = null;
    while(i < k) {
        i++;
        result = h.pop()
    }
    return result;
};